package week_08;

/**
 * 5. 最长回文子串
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 * 示例 2：
 * <p>
 * 输入：s = "cbbd"
 * 输出："bb"
 * 示例 3：
 * <p>
 * 输入：s = "a"
 * 输出："a"
 * 示例 4：
 * <p>
 * 输入：s = "ac"
 * 输出："a"
 */
public class LongestPalindrome_nxn_center_5 {
    public String longestPalindrome(String s) {
        // 分奇偶数情况为中心向外扩
        if (s == null || s.length() < 1) {
            return "";
        }
        int n = s.length();
        int ansSize = 0;
        int idx = 0;
        char[] arr = s.toCharArray();
        //奇数情况
        //"babad"
        for (int center = 0; center < n; center++) {
            int l = center - 1;
            int r = center + 1;
            while (l >= 0 && r < n && arr[l] == arr[r]) {
                l--;
                r++;
            }
            // 停在 l-1 : r+1 越界位置
            if (r - l - 1 > ansSize) {
                idx = l + 1;
                ansSize = r - l - 1;
            }

        }

        // 偶数情况
        // "c*b*b*d"
        for (int center = 0; center < n; center++) {
            int l = center;
            int r = center + 1;
            while (l >= 0 && r < n && arr[l] == arr[r]) {
                l--;
                r++;
            }
            if (r - l - 1 > ansSize) {
                idx = l + 1;
                ansSize = r - l - 1;
            }
        }
        return s.substring(idx, idx + ansSize);
    }
}
